We consider the problem of computing a maximal independent set (MIS) in anextremely harsh broadcast model that relies only on carrier sensing. The modelconsists of an anonymous broadcast network in which nodes have no knowledgeabout the topology of the network or even an upper bound on its size.Furthermore, it is assumed that an adversary chooses at which time slot eachnode wakes up. At each time slot a node can either beep, that is, emit asignal, or be silent. At a particular time slot, beeping nodes receive nofeedback, while silent nodes can only differentiate between none of itsneighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is notpossible to locally converge to an MIS in sub-polynomial time. We then studyfour different relaxations of the model which allow us to circumvent the lowerbound and find an MIS in polylogarithmic time. First, we show that if apolynomial upper bound on the network size is known, it is possible to find anMIS in O(log^3 n) time. Second, if we assume sleeping nodes are awoken byneighboring beeps, then we can also find an MIS in O(log^3 n) time. Third, ifin addition to this wakeup assumption we allow sender-side collision detection,that is, beeping nodes can distinguish whether at least one neighboring node isbeeping concurrently or not, we can find an MIS in O(log^2 n) time. Finally, ifinstead we endow nodes with synchronous clocks, it is also possible to find anMIS in O(log^2 n) time.
展开▼
